package tree;

import javax.swing.tree.TreeCellRenderer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 对称二叉树
public class leetcode101 {
    public static void main(String[] args) {
        Integer[] nums = {1,2,2,3,4,4,3};
        TreeNode root = createTree(nums);
        System.out.println("树创建完毕");
        System.out.println(isSymmetric(root));
    }

    public static TreeNode createTree(Integer[] nums){
        if(nums == null || nums.length == 0) return null;

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while(!queue.isEmpty() && i < nums.length){
            TreeNode curr = queue.poll();

            if(i<nums.length && nums[i] != null){
                curr.left = new TreeNode(nums[i]);
                queue.offer(curr.left);
            }
            i++;
            if(i<nums.length && nums[i] != null){
                curr.right = new TreeNode(nums[i]);
                queue.offer(curr.right);
            }
            i++;
        }
        return root;
    }

    public static boolean isSymmetric(TreeNode root){
        if(root == null || (root.left == null && root.right == null)) return true;
        return isMirror(root.left, root.right);
    }

    public static boolean isMirror(TreeNode left, TreeNode right){
        if(left == null && right == null) return true;
        if(left == null && right != null) return false;
        if(left != null && right == null) return false;
        if(left.val != right.val) return false;

        return isMirror(left.left, right.right)&&isMirror(left.right, right.left);
    }
}